// Copyright: (2012-2015) Ben Strasser <code@ben-strasser.net>
// License: BSD-3
//
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// 1. Redistributions of source code must retain the above copyright notice,
//    this list of conditions and the following disclaimer.
//
//2. Redistributions in binary form must reproduce the above copyright notice,
//   this list of conditions and the following disclaimer in the documentation
//   and/or other materials provided with the distribution.
//
//3. Neither the name of the copyright holder nor the names of its contributors
//   may be used to endorse or promote products derived from this software
//   without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
// AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
// LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
// CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
// SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
// CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
// ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

#ifndef CSV_H
#define CSV_H

#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <utility>
#include <cstdio>
#include <exception>
#ifndef CSV_IO_NO_THREAD
#include <mutex>
#include <thread>
#include <condition_variable>
#endif
#include <memory>
#include <cassert>
#include <cerrno>
#include <istream>

namespace io
{
////////////////////////////////////////////////////////////////////////////
//                                 LineReader                             //
////////////////////////////////////////////////////////////////////////////

namespace error
{
struct base : std::exception
{
    virtual void format_error_message()const = 0;

    const char*what()const throw()
    {
        format_error_message();
        return error_message_buffer;
    }

    mutable char error_message_buffer[512];
};

const int max_file_name_length = 255;

struct with_file_name
{
    with_file_name()
    {
        std::memset(file_name, 0, sizeof(file_name));
    }

    void set_file_name(const char*file_name)
    {
        if(file_name != nullptr)
        {
            strncpy(this->file_name, file_name, sizeof(this->file_name));
            this->file_name[sizeof(this->file_name)-1] = '\0';
        }
        else
        {
            this->file_name[0] = '\0';
        }
    }

    char file_name[max_file_name_length+1];
};

struct with_file_line
{
    with_file_line()
    {
        file_line = -1;
    }

    void set_file_line(int file_line)
    {
        this->file_line = file_line;
    }

    int file_line;
};

struct with_errno
{
    with_errno()
    {
        errno_value = 0;
    }

    void set_errno(int errno_value)
    {
        this->errno_value = errno_value;
    }

    int errno_value;
};

struct can_not_open_file :
    base,
    with_file_name,
    with_errno
{
    void format_error_message()const
    {
        if(errno_value != 0)
            std::snprintf(error_message_buffer, sizeof(error_message_buffer),
                          "Can not open file \"%s\" because \"%s\"."
                          , file_name, std::strerror(errno_value));
        else
            std::snprintf(error_message_buffer, sizeof(error_message_buffer),
                          "Can not open file \"%s\"."
                          , file_name);
    }
};

struct line_length_limit_exceeded :
    base,
    with_file_name,
    with_file_line
{
    void format_error_message()const
    {
        std::snprintf(error_message_buffer, sizeof(error_message_buffer),
                      "Line number %d in file \"%s\" exceeds the maximum length of 2^24-1."
                      , file_line, file_name);
    }
};
}

class ByteSourceBase
{
public:
    virtual int read(char*buffer, int size)=0;
    virtual ~ByteSourceBase() {}
};

namespace detail
{

class OwningStdIOByteSourceBase : public ByteSourceBase
{
public:
    explicit OwningStdIOByteSourceBase(FILE*file):file(file)
    {
        // Tell the std library that we want to do the buffering ourself.
        std::setvbuf(file, 0, _IONBF, 0);
    }

    int read(char*buffer, int size)
    {
        return std::fread(buffer, 1, size, file);
    }

    ~OwningStdIOByteSourceBase()
    {
        std::fclose(file);
    }

private:
    FILE*file;
};

class NonOwningIStreamByteSource : public ByteSourceBase
{
public:
    explicit NonOwningIStreamByteSource(std::istream&in):in(in) {}

    int read(char*buffer, int size)
    {
        in.read(buffer, size);
        return in.gcount();
    }

    ~NonOwningIStreamByteSource() {}

private:
    std::istream&in;
};

class NonOwningStringByteSource : public ByteSourceBase
{
public:
    NonOwningStringByteSource(const char*str, long long size):str(str), remaining_byte_count(size) {}

    int read(char*buffer, int desired_byte_count)
    {
        int to_copy_byte_count = desired_byte_count;
        if(remaining_byte_count < to_copy_byte_count)
            to_copy_byte_count = remaining_byte_count;
        std::memcpy(buffer, str, to_copy_byte_count);
        remaining_byte_count -= to_copy_byte_count;
        str += to_copy_byte_count;
        return to_copy_byte_count;
    }

    ~NonOwningStringByteSource() {}

private:
    const char*str;
    long long remaining_byte_count;
};

#ifndef CSV_IO_NO_THREAD
class AsynchronousReader
{
public:
    void init(std::unique_ptr<ByteSourceBase>arg_byte_source)
    {
        std::unique_lock<std::mutex>guard(lock);
        byte_source = std::move(arg_byte_source);
        desired_byte_count = -1;
        termination_requested = false;
        worker = std::thread(
                     [&]
        {
            std::unique_lock<std::mutex>guard(lock);
            try
            {
                for(;;)
                {
                    read_requested_condition.wait(
                        guard,
                        [&]
                    {
                        return desired_byte_count != -1 || termination_requested;
                    }
                    );
                    if(termination_requested)
                        return;

                    read_byte_count = byte_source->read(buffer, desired_byte_count);
                    desired_byte_count = -1;
                    if(read_byte_count == 0)
                        break;
                    read_finished_condition.notify_one();
                }
            }
            catch(...)
            {
                read_error = std::current_exception();
            }
            read_finished_condition.notify_one();
        }
                 );
    }

    bool is_valid()const
    {
        return byte_source != nullptr;
    }

    void start_read(char*arg_buffer, int arg_desired_byte_count)
    {
        std::unique_lock<std::mutex>guard(lock);
        buffer = arg_buffer;
        desired_byte_count = arg_desired_byte_count;
        read_byte_count = -1;
        read_requested_condition.notify_one();
    }

    int finish_read()
    {
        std::unique_lock<std::mutex>guard(lock);
        read_finished_condition.wait(
            guard,
            [&]
        {
            return read_byte_count != -1 || read_error;
        }
        );
        if(read_error)
            std::rethrow_exception(read_error);
        else
            return read_byte_count;
    }

    ~AsynchronousReader()
    {
        if(byte_source != nullptr)
        {
            {
                std::unique_lock<std::mutex>guard(lock);
                termination_requested = true;
            }
            read_requested_condition.notify_one();
            worker.join();
        }
    }

private:
    std::unique_ptr<ByteSourceBase>byte_source;

    std::thread worker;

    bool termination_requested;
    std::exception_ptr read_error;
    char*buffer;
    int desired_byte_count;
    int read_byte_count;

    std::mutex lock;
    std::condition_variable read_finished_condition;
    std::condition_variable read_requested_condition;
};
#endif

class SynchronousReader
{
public:
    void init(std::unique_ptr<ByteSourceBase>arg_byte_source)
    {
        byte_source = std::move(arg_byte_source);
    }

    bool is_valid()const
    {
        return byte_source != nullptr;
    }

    void start_read(char*arg_buffer, int arg_desired_byte_count)
    {
        buffer = arg_buffer;
        desired_byte_count = arg_desired_byte_count;
    }

    int finish_read()
    {
        return byte_source->read(buffer, desired_byte_count);
    }
private:
    std::unique_ptr<ByteSourceBase>byte_source;
    char*buffer;
    int desired_byte_count;
};
}

class LineReader
{
private:
    static const int block_len = 1<<24;
    std::unique_ptr<char[]>buffer; // must be constructed before (and thus destructed after) the reader!
#ifdef CSV_IO_NO_THREAD
    detail::SynchronousReader reader;
#else
    detail::AsynchronousReader reader;
#endif
    int data_begin;
    int data_end;

    char file_name[error::max_file_name_length+1];
    unsigned file_line;

    static std::unique_ptr<ByteSourceBase> open_file(const char*file_name)
    {
        // We open the file in binary mode as it makes no difference under *nix
        // and under Windows we handle \r\n newlines ourself.
        FILE*file = std::fopen(file_name, "rb");
        if(file == 0)
        {
            int x = errno; // store errno as soon as possible, doing it after constructor call can fail.
            error::can_not_open_file err;
            err.set_errno(x);
            err.set_file_name(file_name);
            throw err;
        }
        return std::unique_ptr<ByteSourceBase>(new detail::OwningStdIOByteSourceBase(file));
    }

    void init(std::unique_ptr<ByteSourceBase>byte_source)
    {
        file_line = 0;

        buffer = std::unique_ptr<char[]>(new char[3*block_len]);
        data_begin = 0;
        data_end = byte_source->read(buffer.get(), 2*block_len);

        // Ignore UTF-8 BOM
        if(data_end >= 3 && buffer[0] == '\xEF' && buffer[1] == '\xBB' && buffer[2] == '\xBF')
            data_begin = 3;

        if(data_end == 2*block_len)
        {
            reader.init(std::move(byte_source));
            reader.start_read(buffer.get() + 2*block_len, block_len);
        }
    }

public:
    LineReader() = delete;
    LineReader(const LineReader&) = delete;
    LineReader&operator=(const LineReader&) = delete;

    explicit LineReader(const char*file_name)
    {
        set_file_name(file_name);
        init(open_file(file_name));
    }

    explicit LineReader(const std::string&file_name)
    {
        set_file_name(file_name.c_str());
        init(open_file(file_name.c_str()));
    }

    LineReader(const char*file_name, std::unique_ptr<ByteSourceBase>byte_source)
    {
        set_file_name(file_name);
        init(std::move(byte_source));
    }

    LineReader(const std::string&file_name, std::unique_ptr<ByteSourceBase>byte_source)
    {
        set_file_name(file_name.c_str());
        init(std::move(byte_source));
    }

    LineReader(const char*file_name, const char*data_begin, const char*data_end)
    {
        set_file_name(file_name);
        init(std::unique_ptr<ByteSourceBase>(new detail::NonOwningStringByteSource(data_begin, data_end-data_begin)));
    }

    LineReader(const std::string&file_name, const char*data_begin, const char*data_end)
    {
        set_file_name(file_name.c_str());
        init(std::unique_ptr<ByteSourceBase>(new detail::NonOwningStringByteSource(data_begin, data_end-data_begin)));
    }

    LineReader(const char*file_name, FILE*file)
    {
        set_file_name(file_name);
        init(std::unique_ptr<ByteSourceBase>(new detail::OwningStdIOByteSourceBase(file)));
    }

    LineReader(const std::string&file_name, FILE*file)
    {
        set_file_name(file_name.c_str());
        init(std::unique_ptr<ByteSourceBase>(new detail::OwningStdIOByteSourceBase(file)));
    }

    LineReader(const char*file_name, std::istream&in)
    {
        set_file_name(file_name);
        init(std::unique_ptr<ByteSourceBase>(new detail::NonOwningIStreamByteSource(in)));
    }

    LineReader(const std::string&file_name, std::istream&in)
    {
        set_file_name(file_name.c_str());
        init(std::unique_ptr<ByteSourceBase>(new detail::NonOwningIStreamByteSource(in)));
    }

    void set_file_name(const std::string&file_name)
    {
        set_file_name(file_name.c_str());
    }

    void set_file_name(const char*file_name)
    {
        if(file_name != nullptr)
        {
            strncpy(this->file_name, file_name, sizeof(this->file_name));
            this->file_name[sizeof(this->file_name)-1] = '\0';
        }
        else
        {
            this->file_name[0] = '\0';
        }
    }

    const char*get_truncated_file_name()const
    {
        return file_name;
    }

    void set_file_line(unsigned file_line)
    {
        this->file_line = file_line;
    }

    unsigned get_file_line()const
    {
        return file_line;
    }

    char*next_line()
    {
        if(data_begin == data_end)
            return 0;

        ++file_line;

        assert(data_begin < data_end);
        assert(data_end <= block_len*2);

        if(data_begin >= block_len)
        {
            std::memcpy(buffer.get(), buffer.get()+block_len, block_len);
            data_begin -= block_len;
            data_end -= block_len;
            if(reader.is_valid())
            {
                data_end += reader.finish_read();
                std::memcpy(buffer.get()+block_len, buffer.get()+2*block_len, block_len);
                reader.start_read(buffer.get() + 2*block_len, block_len);
            }
        }

        int line_end = data_begin;
        while(buffer[line_end] != '\n' && line_end != data_end)
        {
            ++line_end;
        }

        if(line_end - data_begin + 1 > block_len)
        {
            error::line_length_limit_exceeded err;
            err.set_file_name(file_name);
            err.set_file_line(file_line);
            throw err;
        }

        if(buffer[line_end] == '\n' && line_end != data_end)
        {
            buffer[line_end] = '\0';
        }
        else
        {
            // some files are missing the newline at the end of the
            // last line
            ++data_end;
            buffer[line_end] = '\0';
        }

        // handle windows \r\n-line breaks
        if(line_end != data_begin && buffer[line_end-1] == '\r')
            buffer[line_end-1] = '\0';

        char*ret = buffer.get() + data_begin;
        data_begin = line_end+1;
        return ret;
    }
};


////////////////////////////////////////////////////////////////////////////
//                                 CSV                                    //
////////////////////////////////////////////////////////////////////////////

namespace error
{
const int max_column_name_length = 63;
struct with_column_name
{
    with_column_name()
    {
        std::memset(column_name, 0, max_column_name_length+1);
    }

    void set_column_name(const char*column_name)
    {
        if(column_name != nullptr)
        {
            std::strncpy(this->column_name, column_name, max_column_name_length);
            this->column_name[max_column_name_length] = '\0';
        }
        else
        {
            this->column_name[0] = '\0';
        }
    }

    char column_name[max_column_name_length+1];
};


const int max_column_content_length = 63;

struct with_column_content
{
    with_column_content()
    {
        std::memset(column_content, 0, max_column_content_length+1);
    }

    void set_column_content(const char*column_content)
    {
        if(column_content != nullptr)
        {
            std::strncpy(this->column_content, column_content, max_column_content_length);
            this->column_content[max_column_content_length] = '\0';
        }
        else
        {
            this->column_content[0] = '\0';
        }
    }

    char column_content[max_column_content_length+1];
};


struct extra_column_in_header :
    base,
    with_file_name,
    with_column_name
{
    void format_error_message()const
    {
        std::snprintf(error_message_buffer, sizeof(error_message_buffer),
                      "Extra column \"%s\" in header of file \"%s\"."
                      , column_name, file_name);
    }
};

struct missing_column_in_header :
    base,
    with_file_name,
    with_column_name
{
    void format_error_message()const
    {
        std::snprintf(error_message_buffer, sizeof(error_message_buffer),
                      "Missing column \"%s\" in header of file \"%s\"."
                      , column_name, file_name);
    }
};

struct duplicated_column_in_header :
    base,
    with_file_name,
    with_column_name
{
    void format_error_message()const
    {
        std::snprintf(error_message_buffer, sizeof(error_message_buffer),
                      "Duplicated column \"%s\" in header of file \"%s\"."
                      , column_name, file_name);
    }
};

struct header_missing :
    base,
    with_file_name
{
    void format_error_message()const
    {
        std::snprintf(error_message_buffer, sizeof(error_message_buffer),
                      "Header missing in file \"%s\"."
                      , file_name);
    }
};

struct too_few_columns :
    base,
    with_file_name,
    with_file_line
{
    void format_error_message()const
    {
        std::snprintf(error_message_buffer, sizeof(error_message_buffer),
                      "Too few columns in line %d in file \"%s\"."
                      , file_line, file_name);
    }
};

struct too_many_columns :
    base,
    with_file_name,
    with_file_line
{
    void format_error_message()const
    {
        std::snprintf(error_message_buffer, sizeof(error_message_buffer),
                      "Too many columns in line %d in file \"%s\"."
                      , file_line, file_name);
    }
};

struct escaped_string_not_closed :
    base,
    with_file_name,
    with_file_line
{
    void format_error_message()const
    {
        std::snprintf(error_message_buffer, sizeof(error_message_buffer),
                      "Escaped string was not closed in line %d in file \"%s\"."
                      , file_line, file_name);
    }
};

struct integer_must_be_positive :
    base,
    with_file_name,
    with_file_line,
    with_column_name,
    with_column_content
{
    void format_error_message()const
    {
        std::snprintf(error_message_buffer, sizeof(error_message_buffer),
                      "The integer \"%s\" must be positive or 0 in column \"%s\" in file \"%s\" in line \"%d\"."
                      , column_content, column_name, file_name, file_line);
    }
};

struct no_digit :
    base,
    with_file_name,
    with_file_line,
    with_column_name,
    with_column_content
{
    void format_error_message()const
    {
        std::snprintf(error_message_buffer, sizeof(error_message_buffer),
                      "The integer \"%s\" contains an invalid digit in column \"%s\" in file \"%s\" in line \"%d\"."
                      , column_content, column_name, file_name, file_line);
    }
};

struct integer_overflow :
    base,
    with_file_name,
    with_file_line,
    with_column_name,
    with_column_content
{
    void format_error_message()const
    {
        std::snprintf(error_message_buffer, sizeof(error_message_buffer),
                      "The integer \"%s\" overflows in column \"%s\" in file \"%s\" in line \"%d\"."
                      , column_content, column_name, file_name, file_line);
    }
};

struct integer_underflow :
    base,
    with_file_name,
    with_file_line,
    with_column_name,
    with_column_content
{
    void format_error_message()const
    {
        std::snprintf(error_message_buffer, sizeof(error_message_buffer),
                      "The integer \"%s\" underflows in column \"%s\" in file \"%s\" in line \"%d\"."
                      , column_content, column_name, file_name, file_line);
    }
};

struct invalid_single_character :
    base,
    with_file_name,
    with_file_line,
    with_column_name,
    with_column_content
{
    void format_error_message()const
    {
        std::snprintf(error_message_buffer, sizeof(error_message_buffer),
                      "The content \"%s\" of column \"%s\" in file \"%s\" in line \"%d\" is not a single character."
                      , column_content, column_name, file_name, file_line);
    }
};
}

typedef unsigned ignore_column;
static const ignore_column ignore_no_column = 0;
static const ignore_column ignore_extra_column = 1;
static const ignore_column ignore_missing_column = 2;

template<char ... trim_char_list>
struct trim_chars
{
private:
    constexpr static bool is_trim_char(char)
    {
        return false;
    }

    template<class ...OtherTrimChars>
    constexpr static bool is_trim_char(char c, char trim_char, OtherTrimChars...other_trim_chars)
    {
        return c == trim_char || is_trim_char(c, other_trim_chars...);
    }

public:
    static void trim(char*&str_begin, char*&str_end)
    {
        while(str_begin != str_end && is_trim_char(*str_begin, trim_char_list...))
            ++str_begin;
        while(str_begin != str_end && is_trim_char(*(str_end-1), trim_char_list...))
            --str_end;
        *str_end = '\0';
    }
};


struct no_comment
{
    static bool is_comment(const char*)
    {
        return false;
    }
};

template<char ... comment_start_char_list>
struct single_line_comment
{
private:
    constexpr static bool is_comment_start_char(char)
    {
        return false;
    }

    template<class ...OtherCommentStartChars>
    constexpr static bool is_comment_start_char(char c, char comment_start_char, OtherCommentStartChars...other_comment_start_chars)
    {
        return c == comment_start_char || is_comment_start_char(c, other_comment_start_chars...);
    }

public:

    static bool is_comment(const char*line)
    {
        return is_comment_start_char(*line, comment_start_char_list...);
    }
};

struct empty_line_comment
{
    static bool is_comment(const char*line)
    {
        if(*line == '\0')
            return true;
        while(*line == ' ' || *line == '\t')
        {
            ++line;
            if(*line == 0)
                return true;
        }
        return false;
    }
};

template<char ... comment_start_char_list>
struct single_and_empty_line_comment
{
    static bool is_comment(const char*line)
    {
        return single_line_comment<comment_start_char_list...>::is_comment(line) || empty_line_comment::is_comment(line);
    }
};

template<char sep>
struct no_quote_escape
{
    static const char*find_next_column_end(const char*col_begin)
    {
        while(*col_begin != sep && *col_begin != '\0')
            ++col_begin;
        return col_begin;
    }

    static void unescape(char*&, char*&)
    {

    }
};

template<char sep, char quote>
struct double_quote_escape
{
    static const char*find_next_column_end(const char*col_begin)
    {
        while(*col_begin != sep && *col_begin != '\0')
            if(*col_begin != quote)
                ++col_begin;
            else
            {
                do
                {
                    ++col_begin;
                    while(*col_begin != quote)
                    {
                        if(*col_begin == '\0')
                            throw error::escaped_string_not_closed();
                        ++col_begin;
                    }
                    ++col_begin;
                }
                while(*col_begin == quote);
            }
        return col_begin;
    }

    static void unescape(char*&col_begin, char*&col_end)
    {
        if(col_end - col_begin >= 2)
        {
            if(*col_begin == quote && *(col_end-1) == quote)
            {
                ++col_begin;
                --col_end;
                char*out = col_begin;
                for(char*in = col_begin; in!=col_end; ++in)
                {
                    if(*in == quote && (in+1) != col_end && *(in+1) == quote)
                    {
                        ++in;
                    }
                    *out = *in;
                    ++out;
                }
                col_end = out;
                *col_end = '\0';
            }
        }

    }
};

struct throw_on_overflow
{
    template<class T>
    static void on_overflow(T&)
    {
        throw error::integer_overflow();
    }

    template<class T>
    static void on_underflow(T&)
    {
        throw error::integer_underflow();
    }
};

struct ignore_overflow
{
    template<class T>
    static void on_overflow(T&) {}

    template<class T>
    static void on_underflow(T&) {}
};

struct set_to_max_on_overflow
{
    template<class T>
    static void on_overflow(T&x)
    {
        x = std::numeric_limits<T>::max();
    }

    template<class T>
    static void on_underflow(T&x)
    {
        x = std::numeric_limits<T>::min();
    }
};


namespace detail
{
template<class quote_policy>
void chop_next_column(
    char*&line, char*&col_begin, char*&col_end
)
{
    assert(line != nullptr);

    col_begin = line;
    // the col_begin + (... - col_begin) removes the constness
    col_end = col_begin + (quote_policy::find_next_column_end(col_begin) - col_begin);

    if(*col_end == '\0')
    {
        line = nullptr;
    }
    else
    {
        *col_end = '\0';
        line = col_end + 1;
    }
}

template<class trim_policy, class quote_policy>
void parse_line(
    char*line,
    char**sorted_col,
    const std::vector<int>&col_order
)
{
    for(std::size_t i=0; i<col_order.size(); ++i)
    {
        if(line == nullptr)
            throw ::io::error::too_few_columns();
        char*col_begin, *col_end;
        chop_next_column<quote_policy>(line, col_begin, col_end);

        if(col_order[i] != -1)
        {
            trim_policy::trim(col_begin, col_end);
            quote_policy::unescape(col_begin, col_end);

            sorted_col[col_order[i]] = col_begin;
        }
    }
    if(line != nullptr)
        throw ::io::error::too_many_columns();
}

template<unsigned column_count, class trim_policy, class quote_policy>
void parse_header_line(
    char*line,
    std::vector<int>&col_order,
    const std::string*col_name,
    ignore_column ignore_policy
)
{
    col_order.clear();

    bool found[column_count];
    std::fill(found, found + column_count, false);
    while(line)
    {
        char*col_begin,*col_end;
        chop_next_column<quote_policy>(line, col_begin, col_end);

        trim_policy::trim(col_begin, col_end);
        quote_policy::unescape(col_begin, col_end);

        for(unsigned i=0; i<column_count; ++i)
            if(col_begin == col_name[i])
            {
                if(found[i])
                {
                    error::duplicated_column_in_header err;
                    err.set_column_name(col_begin);
                    throw err;
                }
                found[i] = true;
                col_order.push_back(i);
                col_begin = 0;
                break;
            }
        if(col_begin)
        {
            if(ignore_policy & ::io::ignore_extra_column)
                col_order.push_back(-1);
            else
            {
                error::extra_column_in_header err;
                err.set_column_name(col_begin);
                throw err;
            }
        }
    }
    if(!(ignore_policy & ::io::ignore_missing_column))
    {
        for(unsigned i=0; i<column_count; ++i)
        {
            if(!found[i])
            {
                error::missing_column_in_header err;
                err.set_column_name(col_name[i].c_str());
                throw err;
            }
        }
    }
}

template<class overflow_policy>
void parse(char*col, char &x)
{
    if(!*col)
        throw error::invalid_single_character();
    x = *col;
    ++col;
    if(*col)
        throw error::invalid_single_character();
}

template<class overflow_policy>
void parse(char*col, std::string&x)
{
    x = col;
}

template<class overflow_policy>
void parse(char*col, const char*&x)
{
    x = col;
}

template<class overflow_policy>
void parse(char*col, char*&x)
{
    x = col;
}

template<class overflow_policy, class T>
void parse_unsigned_integer(const char*col, T&x)
{
    x = 0;
    while(*col != '\0')
    {
        if('0' <= *col && *col <= '9')
        {
            T y = *col - '0';
            if(x > (std::numeric_limits<T>::max()-y)/10)
            {
                overflow_policy::on_overflow(x);
                return;
            }
            x = 10*x+y;
        }
        else
            throw error::no_digit();
        ++col;
    }
}

template<class overflow_policy>void parse(char*col, unsigned char &x)
{
    parse_unsigned_integer<overflow_policy>(col, x);
}
template<class overflow_policy>void parse(char*col, unsigned short &x)
{
    parse_unsigned_integer<overflow_policy>(col, x);
}
template<class overflow_policy>void parse(char*col, unsigned int &x)
{
    parse_unsigned_integer<overflow_policy>(col, x);
}
template<class overflow_policy>void parse(char*col, unsigned long &x)
{
    parse_unsigned_integer<overflow_policy>(col, x);
}
template<class overflow_policy>void parse(char*col, unsigned long long &x)
{
    parse_unsigned_integer<overflow_policy>(col, x);
}

template<class overflow_policy, class T>
void parse_signed_integer(const char*col, T&x)
{
    if(*col == '-')
    {
        ++col;

        x = 0;
        while(*col != '\0')
        {
            if('0' <= *col && *col <= '9')
            {
                T y = *col - '0';
                if(x < (std::numeric_limits<T>::min()+y)/10)
                {
                    overflow_policy::on_underflow(x);
                    return;
                }
                x = 10*x-y;
            }
            else
                throw error::no_digit();
            ++col;
        }
        return;
    }
    else if(*col == '+')
        ++col;
    parse_unsigned_integer<overflow_policy>(col, x);
}

template<class overflow_policy>void parse(char*col, signed char &x)
{
    parse_signed_integer<overflow_policy>(col, x);
}
template<class overflow_policy>void parse(char*col, signed short &x)
{
    parse_signed_integer<overflow_policy>(col, x);
}
template<class overflow_policy>void parse(char*col, signed int &x)
{
    parse_signed_integer<overflow_policy>(col, x);
}
template<class overflow_policy>void parse(char*col, signed long &x)
{
    parse_signed_integer<overflow_policy>(col, x);
}
template<class overflow_policy>void parse(char*col, signed long long &x)
{
    parse_signed_integer<overflow_policy>(col, x);
}

template<class T>
void parse_float(const char*col, T&x)
{
    bool is_neg = false;
    if(*col == '-')
    {
        is_neg = true;
        ++col;
    }
    else if(*col == '+')
        ++col;

    x = 0;
    while('0' <= *col && *col <= '9')
    {
        int y = *col - '0';
        x *= 10;
        x += y;
        ++col;
    }

    if(*col == '.'|| *col == ',')
    {
        ++col;
        T pos = 1;
        while('0' <= *col && *col <= '9')
        {
            pos /= 10;
            int y = *col - '0';
            ++col;
            x += y*pos;
        }
    }

    if(*col == 'e' || *col == 'E')
    {
        ++col;
        int e;

        parse_signed_integer<set_to_max_on_overflow>(col, e);

        if(e != 0)
        {
            T base;
            if(e < 0)
            {
                base = 0.1;
                e = -e;
            }
            else
            {
                base = 10;
            }

            while(e != 1)
            {
                if((e & 1) == 0)
                {
                    base = base*base;
                    e >>= 1;
                }
                else
                {
                    x *= base;
                    --e;
                }
            }
            x *= base;
        }
    }
    else
    {
        if(*col != '\0')
            throw error::no_digit();
    }

    if(is_neg)
        x = -x;
}

template<class overflow_policy> void parse(char*col, float&x)
{
    parse_float(col, x);
}
template<class overflow_policy> void parse(char*col, double&x)
{
    parse_float(col, x);
}
template<class overflow_policy> void parse(char*col, long double&x)
{
    parse_float(col, x);
}

template<class overflow_policy, class T>
void parse(char*col, T&x)
{
    // Mute unused variable compiler warning
    (void)col;
    (void)x;
    // GCC evalutes "false" when reading the template and
    // "sizeof(T)!=sizeof(T)" only when instantiating it. This is why
    // this strange construct is used.
    static_assert(sizeof(T)!=sizeof(T),
                  "Can not parse this type. Only buildin integrals, floats, char, char*, const char* and std::string are supported");
}

}

template<unsigned column_count,
         class trim_policy = trim_chars<' ', '\t'>,
         class quote_policy = no_quote_escape<','>,
         class overflow_policy = throw_on_overflow,
         class comment_policy = no_comment
         >
class CSVReader
{
private:
    LineReader in;

    char*row[column_count];
    std::string column_names[column_count];

    std::vector<int>col_order;

    template<class ...ColNames>
    void set_column_names(std::string s, ColNames...cols)
    {
        column_names[column_count-sizeof...(ColNames)-1] = std::move(s);
        set_column_names(std::forward<ColNames>(cols)...);
    }

    void set_column_names() {}


public:
    CSVReader() = delete;
    CSVReader(const CSVReader&) = delete;
    CSVReader&operator=(const CSVReader&);

    template<class ...Args>
    explicit CSVReader(Args&&...args):in(std::forward<Args>(args)...)
    {
        std::fill(row, row+column_count, nullptr);
        col_order.resize(column_count);
        for(unsigned i=0; i<column_count; ++i)
            col_order[i] = i;
        for(unsigned i=1; i<=column_count; ++i)
            column_names[i-1] = "col"+std::to_string(i);
    }

    char*next_line()
    {
        return in.next_line();
    }

    template<class ...ColNames>
    void read_header(ignore_column ignore_policy, ColNames...cols)
    {
        static_assert(sizeof...(ColNames)>=column_count, "not enough column names specified");
        static_assert(sizeof...(ColNames)<=column_count, "too many column names specified");
        try
        {
            set_column_names(std::forward<ColNames>(cols)...);

            char*line;
            do
            {
                line = in.next_line();
                if(!line)
                    throw error::header_missing();
            }
            while(comment_policy::is_comment(line));

            detail::parse_header_line
            <column_count, trim_policy, quote_policy>
            (line, col_order, column_names, ignore_policy);
        }
        catch(error::with_file_name&err)
        {
            err.set_file_name(in.get_truncated_file_name());
            throw;
        }
    }

    template<class ...ColNames>
    void set_header(ColNames...cols)
    {
        static_assert(sizeof...(ColNames)>=column_count,
                      "not enough column names specified");
        static_assert(sizeof...(ColNames)<=column_count,
                      "too many column names specified");
        set_column_names(std::forward<ColNames>(cols)...);
        std::fill(row, row+column_count, nullptr);
        col_order.resize(column_count);
        for(unsigned i=0; i<column_count; ++i)
            col_order[i] = i;
    }

    bool has_column(const std::string&name) const
    {
        return col_order.end() != std::find(
                   col_order.begin(), col_order.end(),
                   std::find(std::begin(column_names), std::end(column_names), name)
                   - std::begin(column_names));
    }

    void set_file_name(const std::string&file_name)
    {
        in.set_file_name(file_name);
    }

    void set_file_name(const char*file_name)
    {
        in.set_file_name(file_name);
    }

    const char*get_truncated_file_name()const
    {
        return in.get_truncated_file_name();
    }

    void set_file_line(unsigned file_line)
    {
        in.set_file_line(file_line);
    }

    unsigned get_file_line()const
    {
        return in.get_file_line();
    }

private:
    void parse_helper(std::size_t) {}

    template<class T, class ...ColType>
    void parse_helper(std::size_t r, T&t, ColType&...cols)
    {
        if(row[r])
        {
            try
            {
                try
                {
                    ::io::detail::parse<overflow_policy>(row[r], t);
                }
                catch(error::with_column_content&err)
                {
                    err.set_column_content(row[r]);
                    throw;
                }
            }
            catch(error::with_column_name&err)
            {
                err.set_column_name(column_names[r].c_str());
                throw;
            }
        }
        parse_helper(r+1, cols...);
    }


public:
    template<class ...ColType>
    bool read_row(ColType& ...cols)
    {
        static_assert(sizeof...(ColType)>=column_count,
                      "not enough columns specified");
        static_assert(sizeof...(ColType)<=column_count,
                      "too many columns specified");
        try
        {
            try
            {

                char*line;
                do
                {
                    line = in.next_line();
                    if(!line)
                        return false;
                }
                while(comment_policy::is_comment(line));

                detail::parse_line<trim_policy, quote_policy>
                (line, row, col_order);

                parse_helper(0, cols...);
            }
            catch(error::with_file_name&err)
            {
                err.set_file_name(in.get_truncated_file_name());
                throw;
            }
        }
        catch(error::with_file_line&err)
        {
            err.set_file_line(in.get_file_line());
            throw;
        }

        return true;
    }
};
}
#endif

